package leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * @id: 52
 * @title: N皇后 II
 */
 
//n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 回溯 
// 👍 323 👎 0

public class P52NQueensIi {
    public static void main(String[] args) {
        Solution solution = new P52NQueensIi().new Solution();
        // todo 
        System.out.println(solution.totalNQueens(4));
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int count;
    public int totalNQueens(int n) {
        if (n == 1) {
            return 1;
        }
        Set<Integer> clus = new HashSet<>();
        Set<Integer> pies = new HashSet<>();
        Set<Integer> nas = new HashSet<>();
        backtrack(n, 0, clus, pies, nas);
        return count;
    }

    private void backtrack(int n,
                           int level,
                           Set<Integer> clus,
                           Set<Integer> pies,
                           Set<Integer> nas) {
        if (level == n) {
            ++count;
            return;
        }
        for (int clu = 0; clu < n; ++clu) {
            if (clus.contains(clu)
                    || pies.contains(level+clu)
                    || nas.contains(level-clu)) {
                continue;
            }
            // 构建前置条件
            clus.add(clu);
            pies.add(level+clu);
            nas.add(level-clu);
            backtrack(n, level+1, clus, pies, nas);
            // 回到上层前这层的缓存
            clus.remove(clu);
            pies.remove(level+clu);
            nas.remove(level-clu);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}